#include <stdio.h>

// 把参考值放到合适的位置

void qsort(int *array, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int low = left, hight = right;
    int pivot = array[left];
    while (low < hight) // 找到当前值合适位置
    {
        // 从右向左找到一个比参考值val小的值，并和参考值进行交换。
        // val 存储参考值，不必考虑交换后值丢失
        while (array[hight] >= pivot && hight > low)
            hight--;
        array[low] = array[hight];

        // 从左向右找到一个比参考值大的值，
        while (array[low] <= pivot && low < hight)
            low++;
        // 并和上面找到小的值位置进行交换
        array[hight] = array[low];
    }
    array[low] = pivot;
    for (int i = left; i < right; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    qsort(array, low + 1, right);
    qsort(array, left, low - 1);
}

void qsort1(int* array, int low, int hight)
{
    if(low >= hight) {
        return;
    }
    int base = array[left];
    int left = low, right = hight;
    while (left < right) {
        if(array[right] >= base && right > left) {
            right--;
        }
        array[left] = array[right];
        if (array[left] <= base && left < right) {
            left++;
        }
        array[right] = array[left]; // 调换位置
    }
    array[left] = base; // base 所在位置
    qsort(array, low, left-1);
    qsort(array, left+1, hight);
}

int main(int argc, char const *argv[])
{
    int test[] = {49, 28, 65, 97, 76, 13, 17, 49};
    int count = sizeof(test) / sizeof(int);
    qsort1(test, 0, count - 1);
    for (size_t i = 0; i < count; i++)
    {
        printf("%d\t", test[i]);
    }
    printf("\n");
    return 0;
}


